### RUN DA with year and grade as input

#############################################
####    LOAD DATA                     #######
#############################################
use Data::Dumper; 

### Input files
my $capacityFile = $ARGV[0];
my $choiceFile = $ARGV[1];
my $priorityFile = $ARGV[2];
my $exportFile = $ARGV[3];


my $choice = "$choiceFile";
my $capacity = "$capacityFile";
my $priority = "$priorityFile";
my $outfile = "$exportFile";

# DATA FORMAT, ALL SPACE SEPARATED

# Choice file:
# Long format:
# stu1,ch1
# stu1,ch2
# stu2,ch1

# Capacity file:
# Format: Schoolname,capacity,

# Priority file:
# Long format:
# sch1,ch1
# sch1,ch2
# sch2,ch1


# Variables in use
# @stulist : list of students
# @schlist : list of schools
# @list    : The whole list of students and schools
# %capacity: school capacities PLUS each student has a capacity of 1
# %pref    : reference to the stu's preference list, @{$pref{$stu}} for each stu in @stulist
#                  and to the sch's preference list, @{$pref{$sch}} for each sch in @schlist
#            ${$pref{$agent}[0] is $agent's FIRST choice
#            ${$pref{$agent}[#${$pref{$agent}] is $agent's LAST choice, i.e. itself
#            CAUTION: Each agent's last preferred alternative is itself


$start=time();

my @stulist=(), %pref=(), @schlist=(), %capacity=();
my $agent, $item, $line, @temp=();

# Load @stulist and %pref for students
$agent_temp = "BLANK";
$x=1;
open CHOICE, $choice or die "Choice data file cannot open!";
while (<CHOICE>)
{
    if ($x==0) {++$x;}
    else
    {
        chomp($_);
        @line=split / /, $_;
        $agent=$line[0];
        if ($agent_temp ne $agent) 
        {
            push(@stulist,$agent);
            $agent_temp = $agent;
#            @{$pref{$agent}}=();
        }   
        push(@{$pref{$agent}},$line[1]);
    }
}

foreach $agent (@stulist) {push(@{$pref{$agent}}, $agent);
# print @{$pref{$agent}};<STDIN>;
}
 

# Load @schlist and %pref for schools

$agent_temp = "BLANK";
$x=1;
open PRIORITY, $priority or die "Priority data file cannot open!";
while (<PRIORITY>)
{
    if ($x==0) {++$x;}
    else
    {
        chomp($_);
        @line=split / /, $_;
        $agent=$line[0];
        if ($agent_temp ne $agent) 
        {
            push(@schlist,$agent);
            $agent_temp = $agent;
#            @{$pref{$agent}}=();
        }   
        push(@{$pref{$agent}},$line[1]);
    }
}

foreach $agent (@schlist) {push(@{$pref{$agent}}, $agent);
# print @{$pref{$agent}};<STDIN>;
}


# Load capacities

$x=1;
open CAP, $capacity or die "Capacity file cannot open!";
while (<CAP>)
{
    if ($x==0) {++$x;}
    else
    {
        chomp($_);
        @line=split / /, $_;
        $agent=$line[0];
        $capacity{$agent}=$line[1];
    }

}


# Keep original student preferences
%origpref=();
foreach $stu (@stulist) 
{
    $temp="";
    @{$origpref{$stu}}=();
    foreach $sch (@{$pref{$stu}})
    {
        if (substr($sch,0,4) ne $temp and $sch ne $stu)
        {
            $temp=substr($sch,0,4);
            push(@{$origpref{$stu}},$temp);
        }
    }
}

# Keep priority orderings
foreach $sch (@schlist) {@{$origpref{$sch}}=@{$pref{$sch}};}



###################################################
############# Stu Opt DA (SODA) ###################
###################################################


# Input Variable:
# @stulist : the list of students
# @schlist : the list of schools
# %capacity: school capacities PLUS each student has a capacity of 1
# %pref    : reference to the stu's preference list, @{$pref{$stu}} for each stu in @stulist
#                  and to the sch's preference list, @{$pref{$sch}} for each sch in @schlist
# %type    : "STU" if it is a student; "SCH" if it is a school


# Other variables in use:
# %assign  : reference to the list of students at sch, @{$assign{$sch}} 
#            and to each student's assigned school, ${$assign{$stu}}
# %rank    : reference to $stu's ranking at $sch, ${$rank{$stu ."-". $sch}}

# EACH AGENT'S LAST CHOICE IS ITSELF
# EACH STUDENT'S CAPACITY IS 1
# ${$pref{$agent}[#${$pref{$agent}] is $agent's LAST choice, i.e. itself
# ${$pref{$agent}[0] is $agent's FIRST choice


######################
# Initialize #########
######################

my %assign=(), %rank=();
my @unassigned=@stulist, $stu, $sch, $topch, @temp=(), $cap, $tempstu ;
my $big=5555555;


# initialize %assign

# print "initializing assigment array\n";
foreach $stu (@stulist) {@{$assign{$stu}}=();}   #$type{$stu}="STU";}
foreach $sch (@schlist) {@{$assign{$sch}}=();}   #$type{$sch}="SCH";}



##################################################
# Run SODA (student optimal deferred acceptance) #
##################################################


# print "DAA started\n\n";

while ($#unassigned>-1)
{   # If there is an unassigned student, pick one and place her


#print "number of unassigned $#unassigned \n";
#print "$#unassigned\n";

    $stu=pop(@unassigned);
    $topch=shift(@{$pref{$stu}});

    # if $stu runs out of options assign her to herself
    if ($topch eq $stu) {push(@{$assign{$stu}},$stu);}  
    else
    {   
        # Check if $stu is in the pref list of $topch
        $inflag="NO";
        foreach $tempstu (@{$pref{$topch}})
        {
            if ($stu eq $tempstu) {$inflag="YES";last;}
        }
        
        
        # if $stu is NOT acceptable to $topch, put $stu back into @unassigned    
        if ($inflag eq "NO")
        {   
            unshift(@unassigned,$stu);
        }
        
        # otherwise revise the tentative list at $topch
        else
        {   
            # add $stu to the list
            push(@{$assign{$topch}},$stu);
            
            # find the number of tentatively assigned at $topch
            $current=$#{$assign{$topch}};
            ++$current;
                        
            # if the tentative list exceeds the capacity at $topch, 
            # bump out the lowest rank student

            $cap=$capacity{$topch};
            if ($current>$cap)
            {
                @temp=();
                $x=0;
                %assigned=();
                %reassigned=();
                
                foreach $tempstu (@{$assign{$topch}}) 
                {
                    $assigned{$tempstu}="YES";    
                    $reassigned{$tempstu}="NO";
                }
                
                # reassign students in the order of $topch's preferences
                foreach $tempstu (@{$pref{$topch}})
                {
                    if ($assigned{$tempstu} eq "YES" and $cap>0)
                    {
                        push(@temp,$tempstu);
                        --$cap;
                        $reassigned{$tempstu}="YES";
                    }
                    if ($cap>0) {++$x;}
                    else {last;}
                }
                
                
                # put the unasigned student back to the pool of unassigned
                # there is only one such student
                foreach $tempstu(@{$assign{$topch}})
                {
                    if ($reassigned{$tempstu} eq "NO")
                    {
                       unshift(@unassigned,$tempstu);
                       last; 
                    }
                }
                
                # revised the tentative list
                @{$assign{$topch}}=@temp;

                # crop $topch's prefs, no need to keep every student
                $#{$pref{$topch}}=$x;
            
            
            }        
        }
    }
}



foreach $sch (@schlist)
{
    foreach $stu (@{$assign{$sch}})
        {push(@{$assign{$stu}},$sch);}
}


##########################################################################

### WRITE OUT ALL RESULTS ######

open (OUT, "> $outfile") or die "Cannot open $outfile for write";
print OUT "student_id_scram ourmatch\n";
print "writing $outfile\n";
foreach $stu (@stulist)
{
        print OUT "$stu ${$assign{$stu}}[0]\n";
}
close OUT;


$end=time();
$ellapse=($end-$start)/60;
print "starttime = $start, endtime = $end\nellapse time = $ellapse minutes\n";



#
